import java.util.Deque;
import java.util.LinkedList;

public class Demo02 {
//    3. 二叉树的最近公共祖先
//    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
//    示例 1：
//    输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
//    输出：3
//    解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
//    示例 2：
//    输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
//    输出：5
//    解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
//    示例 3：
//    输入：root = [1,2], p = 1, q = 2
//    输出：1

//    public TreeNode lowestCommonAncestor(TreeNode root,TreeNode p,TreeNode q){
//        if(root==null){
//            return null;
//        }
//        if(root==p||root==q){
//            return root;
//        }
//        TreeNode left=lowestCommonAncestor(root.left,p,q);
//        TreeNode right=lowestCommonAncestor(root.right,p,q);
//        if(left!=null&&right!=null) {
//            return root;
//        } else if (left!=null) {
//            return left;
//        } else if (right!=null) {
//            return right;
//        }
//        return null;
//    }




    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p,TreeNode q){
        Deque<TreeNode> stack1=new LinkedList<>();
        getPath(root,p,stack1);
        Deque<TreeNode> stack2=new LinkedList<>();
        getPath(root,q,stack2);
        int size1 = stack1.size();
        int size2 = stack2.size();
        if(size1 > size2) {
            int size = size1-size2;
            while (size != 0) {
                stack1.pop();
                size--;
            }
        }else {
            int size = size2-size1;
            while (size != 0) {
                stack2.pop();
                size--;
            }
        }
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if(stack1.peek() != stack2.peek()) {
                stack1.pop();
                stack2.pop();
            }else {
                return stack1.peek();
            }
        }
        return null;
    }
    public boolean getPath(TreeNode root, TreeNode node, Deque<TreeNode> stack){
        if(root==null||node==null){
            return false;
        }
        stack.push(root);
        if(root==node){
            return true;
        }
        boolean ret1=getPath(root.left,node,stack);
        if(ret1){
            return true;
        }
        boolean ret2=getPath(root.right,node,stack);
        if(ret2){
            return true;
        }
        stack.pop();
        return false;
    }


}


